package datastructure.sort;

/**
 * @author yinlei
 * @date 2018/7/3
 * @since 1.0.0
 */
public class MergeSort implements SortMain.Sort {
    public void sort(int[] arr) {

        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        if (left >= right) return;

        int mid = (left + right) / 2;

        // 递归查分到每个子串只有1个元素
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        // 合并有序子串
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int[] tem = new int[right - left + 1];
        int temOffset = 0;
        while (i <= mid && j <= right) {
            int pos = i;
            if (arr[i] > arr[j]) {
                pos = j;
                j++;
            } else {
                pos = i;
                i++;
            }
            tem[temOffset++] = arr[pos];
        }

        while (i <= mid) {
            tem[temOffset++] = arr[i++];
        }
        while (j <= right) {
            tem[temOffset++] = arr[j++];
        }

        for (int mi = 0; mi < tem.length; mi++) {
            arr[mi + left] = tem[mi];
        }
    }


}
